package codetop.kuaishou.T233;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-15 22:23:49 星期四
 */
class Solution {
    public int countDigitOne(int n) {
        int[][] table = getTable(String.valueOf(n));
        return getCount(String.valueOf(n), 0, table);
    }

    private int getCount(String num, int pos, int[][] table) {
        int digit = num.charAt(pos) - '0';
        if (pos == num.length() - 1)
            return table[0][digit];
        int count = getCount(num, pos+1, table);
        if (digit == 0)
            return count;
        else if (digit == 1)
            return count + table[num.length()-1-pos][0] + Integer.parseInt(num.substring(pos+1)) + 1;
        else
            return count + table[num.length()-1-pos][digit-1];
    }

    private int[][] getTable(String num) {
        int[][] table = new int[num.length()][10];
        int base = 1;
        for (int i=0; i<num.length(); ++i) {
            if (i > 0)
                table[i][0] = table[i-1][9];
            table[i][1] = table[i][0] * 2 + base;
            for (int j=2; j<10; ++j)
                table[i][j] = table[i][j-1] + table[i][0];
            base *= 10;
        }
        return table;
    }
}